Labuan từng là một phần của Vương quốc Hồi giáo Brunei (một Vương quốc rộng gấp nhiều lần nước Brunei hiện đại). Vào những năm 1840, hòn đảo vốn không có người ở này được đề xuất trở thành một căn cứ cho các hoạt động chống hải tặc của Anh Quốc. Quốc vương Brunei đã nhươngj Labuan cho người Anh năm 1848[4]. Năm 1849, Công ty Quần đảo Phương Đông trở thành công ty đầu tiên mạo hiểm khai thác than ở đây. Về sau lãnh thổ trở thành một trạm trong tuyến cáp ngầm dưới biển giữa Hồng Kông và Singapore.

Trong Chiến tranh Thế giới thứ hai, Labuan bị Nhật Bản chiếm đóng từ tháng 12 năm 1941 đến tháng 6 năm 1945 và người Nhật đã đổi tên nơi này thành Đảo Maida (前田島 [Maeda-shima]). Tháng 6 năm 1945, Labuan lấy lại tên cũ và nằm dưới quyền quản lý của quân đội Anh, sau đó Labuan gia nhập Bắc Borneo thuộc Anh vào ngày 15/7/1946 và trở thành một phần của bang Sabah năm 1963.

Năm 1984, bang Sabah nhượng lại Labuan cho chính quyền liên bang. Năm 1990, Labuan được công bố là một trung tâm tài chính xa bờ quốc tế và mậu dịch tự do. Trung tâm Thương mại và Tài chính Quốc tế Labuan được thành lập năm 1990.